{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #训练计划 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trainningPlan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #训练计划 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个以 <strong>有序链表</strong> 形式记录的训练计划 <code>l1</code>、<code>l2</code>，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 <strong>升序</strong> 记录于链表并返回。</p>\n",
    "\n",
    "<p><strong>注意</strong>：新链表是通过拼接给定的两个链表的所有节点组成的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [1,2,4], l2 = [1,3,4]\n",
    "<strong>输出：</strong>[1,1,2,3,4,4]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [], l2 = []\n",
    "<strong>输出：</strong>[]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [], l2 = [0]\n",
    "<strong>输出：</strong>[0]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><code>0 &lt;= 链表长度 &lt;= 1000</code></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 21 题相同：<a href=\"https://leetcode-cn.com/problems/merge-two-sorted-lists/\">https://leetcode-cn.com/problems/merge-two-sorted-lists/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [he-bing-liang-ge-pai-xu-de-lian-biao-lcof](https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [he-bing-liang-ge-pai-xu-de-lian-biao-lcof](https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4]\\n[1,3,4]', '[]\\n[]', '[]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = cur = ListNode(0)  # 或\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                cur.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                cur.next = l2\n",
    "                l2 = l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        prehead = ListNode(-1)\n",
    "\n",
    "        prev = prehead\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                prev.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                prev.next = l2\n",
    "                l2 = l2.next            \n",
    "            prev = prev.next\n",
    "\n",
    "        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可\n",
    "        prev.next = l1 if l1 is not None else l2\n",
    "\n",
    "        return prehead.next\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dum = ListNode(0)\n",
    "        while l1 and l2:\n",
    "            if l1.val>=l2.val:\n",
    "                cur.next=l2\n",
    "                l2=l2.next\n",
    "            else :\n",
    "                cur.next=l1\n",
    "                l1=l1.next\n",
    "            cur = cur.next\n",
    "        cur.next=l1 if l1 else l2\n",
    "        return dum.next\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l3=copy = ListNode()\n",
    "        while l1 and l2:\n",
    "            if l1.val<=l2.val:\n",
    "               l3.next,l1 = l1,l1.next\n",
    "            else:\n",
    "                l3.next,l2 = l2,l2.next\n",
    "            l3 = l3.next\n",
    "        l3.next = l1 if l1 else l2\n",
    "        return copy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = ListNode(None)\n",
    "        cur = head\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                cur.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                cur.next = l2\n",
    "                l2 = l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 or l2\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        ans = ListNode()\n",
    "        l3 = ans\n",
    "\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                l3.next = l1\n",
    "                l3 = l3.next\n",
    "                l1 = l1.next\n",
    "            \n",
    "            else:\n",
    "                l3.next = l2\n",
    "                l3 = l3.next\n",
    "                l2 = l2.next\n",
    "\n",
    "\n",
    "        if l1:\n",
    "            while l1:\n",
    "                l3.next = l1\n",
    "                l3 = l3.next\n",
    "                l1 = l1.next\n",
    "\n",
    "                \n",
    "\n",
    "        if l2:\n",
    "            while l2:\n",
    "                l3.next = l2\n",
    "                l3 = l3.next\n",
    "                l2 = l2.next\n",
    "\n",
    "        ans = ans.next\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum = cur = ListNode(0)\n",
    "        while l1 and l2:\n",
    "            if l1.val >= l2.val:\n",
    "                cur.next = l2\n",
    "                l2 = l2.next\n",
    "            else:\n",
    "                cur.next = l1\n",
    "                l1 = l1.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if not l2 else l2\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dum = ListNode(0)\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                cur.next, l1 = l1, l1.next\n",
    "            else:\n",
    "                cur.next, l2 = l2, l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2\n",
    "        return dum.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dmp = ListNode()\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                cur.next, l1 = l1, l1.next\n",
    "            else:\n",
    "                cur.next, l2 = l2, l2.next\n",
    "\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2\n",
    "        return dmp.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        p=l1\n",
    "        q=l2\n",
    "        head=ListNode\n",
    "        r=head\n",
    "        while p and q:\n",
    "            if p.val>=q.val:\n",
    "                r.next=q\n",
    "                q=q.next\n",
    "            else:\n",
    "                r.next=p\n",
    "                p=p.next\n",
    "            r=r.next\n",
    "        if p:\n",
    "            r.next=p \n",
    "        else:\n",
    "            r.next=q\n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dum = ListNode(0)  #伪节点\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                cur.next, l1 = l1, l1.next\n",
    "            else:\n",
    "                cur.next, l2 = l2, l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2 \n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=dum=ListNode(0)\n",
    "        while l1 and l2:\n",
    "            if l1.val<=l2.val:\n",
    "                cur.next,l1=l1,l1.next\n",
    "            else:\n",
    "                cur.next,l2=l2,l2.next\n",
    "            cur=cur.next\n",
    "        cur.next=l1 if l1  else l2\n",
    "        return dum.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dum = ListNode(0)\n",
    "        while l1 !=None and l2 != None :\n",
    "           if l1.val < l2.val :#链表中的值比较，不是链表比较\n",
    "              cur.next = l1\n",
    "              l1 = l1.next\n",
    "           else :\n",
    "                cur.next = l2  \n",
    "                l2 = l2.next\n",
    "           cur=cur.next\n",
    "        if l1 ==None: cur.next = l2\n",
    "        if l2 ==None: cur.next = l1\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1 == None:\n",
    "            return l2\n",
    "        elif l2 == None:\n",
    "            return l1\n",
    "\n",
    "        head1 = l1\n",
    "        head2 = l2\n",
    "\n",
    "        begin_head = ListNode(-1)\n",
    "        pre_head = begin_head\n",
    "\n",
    "        while head1 and head2:\n",
    "            if head1.val <= head2.val:\n",
    "                pre_head.next = head1\n",
    "                head1 = head1.next\n",
    "            else:\n",
    "                pre_head.next = head2\n",
    "                head2 = head2.next\n",
    "            pre_head = pre_head.next\n",
    "        pre_head.next = head1 if head1 is not None else head2\n",
    "\n",
    "        return begin_head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur = dum = ListNode(0)\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                cur.next, l1 = l1, l1.next\n",
    "            else:\n",
    "                cur.next, l2 = l2, l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2\n",
    "        return dum.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum = cur = ListNode(0)\n",
    "        while l1 and l2 :\n",
    "            if l1.val < l2.val:\n",
    "                cur.next, l1 = l1, l1.next\n",
    "            else:\n",
    "                cur.next, l2 = l2, l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = ListNode()\n",
    "        n = head\n",
    "        while l1 and l2:\n",
    "            if l1.val < l2.val:\n",
    "                n.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                n.next = l2\n",
    "                l2 = l2.next\n",
    "            n = n.next\n",
    "        if l1:\n",
    "            n.next = l1\n",
    "        if l2:\n",
    "            n.next = l2\n",
    "        return head.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum = cur = ListNode(0)\n",
    "        while l1 and l2 :\n",
    "            if l1.val <= l2.val:\n",
    "                cur.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                cur.next = l2\n",
    "                l2 = l2.next\n",
    "            cur = cur.next\n",
    "        while l1:\n",
    "            cur.next = l1\n",
    "            l1 = l1.next\n",
    "            cur = cur.next\n",
    "        while l2:\n",
    "            cur.next = l2\n",
    "            l2 = l2.next\n",
    "            cur = cur.next\n",
    "\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dum = ListNode(0)\n",
    "        while l1 and l2 :\n",
    "            if l1.val < l2.val:\n",
    "                cur.next, l1 = l1, l1.next\n",
    "            else:\n",
    "                cur.next, l2 = l2, l2.next\n",
    "            cur = cur.next\n",
    "        cur.next = l1 if l1 else l2\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum=ListNode(None)#定义伪头结点和操作时用的指针\n",
    "        cur=dum\n",
    "        while l1 and l2:\n",
    "            if l1.val<l2.val:\n",
    "                cur.next=l1\n",
    "                l1=l1.next\n",
    "            else:\n",
    "                cur.next=l2\n",
    "                l2=l2.next\n",
    "            cur=cur.next\n",
    "        if l1!=None:\n",
    "            cur.next=l1\n",
    "        elif l2!=None:\n",
    "            cur.next=l2\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        virtual = ListNode(0)\n",
    "        ans = virtual\n",
    "        while l1 != None or l2 != None:\n",
    "            if l1 == None:\n",
    "                virtual.next = l2\n",
    "                virtual = l2\n",
    "                l2 = l2.next\n",
    "            elif l2 == None:\n",
    "                virtual.next = l1\n",
    "                virtual = l1\n",
    "                l1 = l1.next\n",
    "            elif l1.val > l2.val:\n",
    "                virtual.next = l2\n",
    "                virtual = l2\n",
    "                l2 = l2.next\n",
    "            else:\n",
    "                virtual.next = l1\n",
    "                virtual = l1\n",
    "                l1 = l1.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum = pre = ListNode()\n",
    "        list1 , list2 = l1, l2\n",
    "        while list1 and list2:\n",
    "            if list1.val <= list2.val:\n",
    "                cur = ListNode(val=list1.val)\n",
    "                list1 = list1.next\n",
    "            else:\n",
    "                cur = ListNode(val=list2.val)\n",
    "                list2 = list2.next\n",
    "            pre.next = cur\n",
    "            pre = cur\n",
    "        while list1:\n",
    "            cur = ListNode(val=list1.val)\n",
    "            list1 = list1.next\n",
    "            pre.next = cur\n",
    "            pre = cur\n",
    "        while list2:\n",
    "            cur = ListNode(val=list2.val)\n",
    "            list2 = list2.next\n",
    "            pre.next = cur\n",
    "            pre = cur\n",
    "        return dum.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def create_linked_list(elements):\n",
    "    if not elements:\n",
    "        return None\n",
    "\n",
    "    # 创建头节点\n",
    "    head = ListNode(elements[0])\n",
    "    current = head\n",
    "\n",
    "    # 添加剩余节点\n",
    "    for element in elements[1:]:\n",
    "        current.next = ListNode(element)\n",
    "        current = current.next\n",
    "\n",
    "    return head\n",
    "\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ls = []\n",
    "        while l1:\n",
    "            ls.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            ls.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ls.sort()\n",
    "        finall = create_linked_list(ls)\n",
    "        return finall\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def create_linked_list(elements):\n",
    "    if not elements:\n",
    "        return None\n",
    "\n",
    "    # 创建头节点\n",
    "    head = ListNode(elements[0])\n",
    "    current = head\n",
    "\n",
    "    # 添加剩余节点\n",
    "    for element in elements[1:]:\n",
    "        current.next = ListNode(element)\n",
    "        current = current.next\n",
    "\n",
    "    return head\n",
    "\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ls = []\n",
    "        while l1:\n",
    "            ls.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            ls.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ls.sort()\n",
    "        finall = create_linked_list(ls)\n",
    "        return finall\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        root = head = ListNode(0)\n",
    "        while l1 or l2:\n",
    "            if l1 is None:\n",
    "                head.next = l2\n",
    "                l2 = None\n",
    "            elif l2 is None:\n",
    "                head.next = l1\n",
    "                l1 = None\n",
    "            else:\n",
    "                val1 = l1.val\n",
    "                val2 = l2.val\n",
    "                if val1 < val2:\n",
    "                    head.next = ListNode(val1)\n",
    "                    l1 = l1.next\n",
    "                else:\n",
    "                    head.next = ListNode(val2)\n",
    "                    l2 = l2.next\n",
    "            head = head.next\n",
    "        return root.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        p1,p2 = l1,l2\n",
    "        if p1.val <=p2.val:\n",
    "            head = ListNode(p1.val)\n",
    "            p1 = p1.next\n",
    "        else:\n",
    "            head = ListNode(p2.val)\n",
    "            p2 = p2.next\n",
    "        cur = head\n",
    "        while p1 and p2:\n",
    "            if p1.val <=p2.val:\n",
    "                cur.next = ListNode(p1.val)\n",
    "                cur = cur.next\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                cur.next = ListNode(p2.val)\n",
    "                cur = cur.next\n",
    "                p2 = p2.next\n",
    "        while p1:\n",
    "            cur.next = ListNode(p1.val)\n",
    "            cur = cur.next\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            cur.next = ListNode(p2.val)\n",
    "            cur = cur.next\n",
    "            p2 = p2.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        lis = []\n",
    "        while l1:\n",
    "            lis.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            lis.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        lis.sort()\n",
    "        l_new = ListNode(0)\n",
    "        root = l_new \n",
    "        for i in range(len(lis)):\n",
    "            temp = ListNode(lis[i])\n",
    "            root.next = temp\n",
    "            root = temp\n",
    "        return l_new.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def create_linked_list(elements):\n",
    "    if not elements:\n",
    "        return None\n",
    "\n",
    "    # 创建头节点\n",
    "    head = ListNode(elements[0])\n",
    "    current = head\n",
    "\n",
    "    # 添加剩余节点\n",
    "    for element in elements[1:]:\n",
    "        current.next = ListNode(element)\n",
    "        current = current.next\n",
    "\n",
    "    return head\n",
    "\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ls = []\n",
    "        while l1:\n",
    "            ls.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            ls.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ls.sort()\n",
    "        finall = create_linked_list(ls)\n",
    "        return finall\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        \n",
    "        s = []\n",
    "        b = []\n",
    "        while l1:\n",
    "            b.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        c = []\n",
    "        while l2:\n",
    "            c.append(l2.val)\n",
    "            l2 =l2.next\n",
    "        b.extend(c)\n",
    "        b.sort()\n",
    "        tHead = None\n",
    "        if len(b):\n",
    "            tHead = ListNode(b[0])\n",
    "        tempHead = tHead\n",
    "        for i in range(1,len(b)):\n",
    "            temp =ListNode(b[i])\n",
    "            tempHead.next=temp\n",
    "            tempHead =temp\n",
    "        return tHead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = ListNode()\n",
    "        node_head = head\n",
    "        while(l1 != None or l2 != None):\n",
    "            if(l1 != None and l2 == None):\n",
    "                node_head.next = ListNode(val=l1.val)\n",
    "                l1 = l1.next\n",
    "                node_head = node_head.next\n",
    "            elif(l2 != None and l1 == None):\n",
    "                node_head.next = ListNode(val=l2.val)\n",
    "                l2 = l2.next\n",
    "                node_head = node_head.next\n",
    "            elif(l1 != None and l2 != None):\n",
    "                if(l1.val <= l2.val):\n",
    "                    node_head.next = ListNode(val=l1.val)\n",
    "                    l1 = l1.next\n",
    "                    node_head = node_head.next\n",
    "                else:\n",
    "                    node_head.next = ListNode(val=l2.val)\n",
    "                    l2 = l2.next\n",
    "                    node_head = node_head.next\n",
    "        return head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        n = []\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                n.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                n.append(l2.val)\n",
    "                l2 = l2.next\n",
    "        n.sort()\n",
    "        if not n: return None\n",
    "        head = ListNode(n[0])\n",
    "        tmp_node = head\n",
    "        for i in range(1, len(n)):\n",
    "            new_node = ListNode(n[i])\n",
    "            tmp_node.next = new_node\n",
    "            tmp_node = tmp_node.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1==None and l2==None:\n",
    "            return l1\n",
    "\n",
    "        rel=[]\n",
    "        def recur(cur):\n",
    "            if cur==None:\n",
    "                return\n",
    "            recur(cur.next)\n",
    "            rel.append(cur.val)           \n",
    "        recur(l1)\n",
    "        recur(l2)\n",
    "        res=sorted(rel)\n",
    "\n",
    "        \n",
    "        head=ListNode(res[0])\n",
    "        temphead=head\n",
    "        for i in range(1,len(res)):\n",
    "            temp=ListNode(res[i])\n",
    "            temphead.next=temp\n",
    "            temphead=temp\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        list1 = l1\n",
    "        list2 = l2\n",
    "        if list1 == None: return list2\n",
    "        if list2==None: return list1\n",
    "        if list1.val < list2.val:\n",
    "            list1.next = self.trainningPlan(list1.next,list2)\n",
    "            return list1\n",
    "        else:\n",
    "            list2.next = self.trainningPlan(list1,list2.next)\n",
    "            return list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        elif l2 is None:\n",
    "            return l1\n",
    "        elif l1.val < l2.val:\n",
    "            l1.next = self.trainningPlan(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.trainningPlan(l2.next, l1)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        if l2 is None:\n",
    "            return l1\n",
    "        if l1.val <= l2.val:\n",
    "            l1.next = self.trainningPlan(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.trainningPlan(l1, l2.next)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not l1: return l2\n",
    "        if not l2: return l1\n",
    "        if l1.val <= l2.val:\n",
    "            l1.next = self.trainningPlan(l1.next, l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.trainningPlan(l1, l2.next)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        elif l2 is None:\n",
    "            return l1\n",
    "        # 返回较小值，不断递归\n",
    "        elif l1.val<l2.val:\n",
    "            l1.next = self.trainningPlan(l1.next,l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next = self.trainningPlan(l1,l2.next)\n",
    "            return l2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        if l1.val<=l2.val:\n",
    "            l1.next=self.trainningPlan(l1.next,l2)\n",
    "            return l1\n",
    "        else:\n",
    "            l2.next=self.trainningPlan(l2.next,l1)\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]):\n",
    "        if l1 and l2:\n",
    "            if l1.val > l2.val:\n",
    "                l1, l2 = l2, l1\n",
    "            l1.next = self.trainningPlan(l1.next, l2)\n",
    "        return l1 or l2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
